package pl.edu.pb.wi.pwnography.modules;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.logging.Logger;

import pl.edu.pb.wi.pwnography.model.ParsedData;

public class KMeansClustering {
    private static final Logger log = Logger.getLogger(KMeansClustering.class
	    .getName());

    public static enum STARTING_POINTS_INIT {
	RANDOM_VALUES, RANDOM_POINTS
    };

    private static final String PREFIX_BASE = "KMEANS_";
    private static final String ATTRIBUTES_SUFFIX = "%dATTRIBUTES";
    private static final String MEANS_SUFFIX = "%dMEANS";
    private static final float MAX_DIFFERENCE = 0.0000009f;
    private static final int ANTI_NEVERENDING_LOOP_ITERATION_COUNT = 100;

    public static Map<String, List<Object>> cluster(ParsedData data,
	    List<String> excludedColumns, int kmeans, String newColumnName,
	    STARTING_POINTS_INIT initType) throws Exception {
	if (kmeans < 1) {
	    throw new Exception("K-means can't be less than 1.");
	}

	List<String> floatColumnNames = data.getFloatTypeColumnNames();
	if (excludedColumns != null) {
	    floatColumnNames.removeAll(excludedColumns);
	}

	/*
	 * Szukamy najwyższej oraz najniższej wartości każdego z atrybutów.
	 * Przyda się do losowania początkowych punktów. Nie chcę przesadzić z
	 * przedziałem z tego powodu losowanie odbędzie się w przedziale <min,
	 * max>
	 */
	float[] maxValues = new float[floatColumnNames.size()];
	float[] minValues = new float[floatColumnNames.size()];
	{
	    int i = 0;
	    for (String columnName : floatColumnNames) {
		for (Object value : data.getColumnValues(columnName)) {
		    if ((Float) value > maxValues[i]) {
			maxValues[i] = (Float) value;
		    }
		    if ((Float) value < minValues[i]) {
			minValues[i] = (Float) value;
		    }
		}
		++i;
	    }
	}

	/*
	 * Losujemy punkty startowe.
	 */
	int rowCount = data.getRowCount();
	float[][] means = new float[kmeans][floatColumnNames.size()];
	Random rand = new Random();
	List<Integer> usedIndexes = new ArrayList<Integer>();
	for (int i = 0; i < kmeans; ++i) {
	    int randomIndex = (i + Math.abs(rand.nextInt())) % rowCount;
	    while (usedIndexes.contains(randomIndex)) {
		randomIndex = (i + Math.abs(rand.nextInt())) % rowCount;
	    }
	    usedIndexes.add(randomIndex);

	    for (int j = 0; j < floatColumnNames.size(); ++j) {
		if (initType == STARTING_POINTS_INIT.RANDOM_VALUES) {
		    means[i][j] = minValues[j] + rand.nextFloat()
			    * (maxValues[j] - minValues[j]);
		}

		if (initType == STARTING_POINTS_INIT.RANDOM_POINTS) {
		    means[i][j] = (Float) data.getCell(floatColumnNames.get(j),
			    randomIndex);
		}
	    }
	}

	int iterations = 0;
	boolean changed = true;
	float[][] distances = new float[kmeans][rowCount];
	while (changed && iterations < ANTI_NEVERENDING_LOOP_ITERATION_COUNT) {
	    log.info(String.format("Starting iteration number %d.", iterations));

	    /*
	     * Obliczamy odległości między punktami, a średnimi.
	     */
	    float[][] distance = new float[kmeans][rowCount];
	    distances = distance;
	    for (int i = 0; i < rowCount; ++i) {
		for (int j = 0; j < floatColumnNames.size(); ++j) {
		    String colName = floatColumnNames.get(j);
		    for (int m = 0; m < kmeans; ++m) {
			float diff = (Float) data.getCell(colName, i)
				- means[m][j];
			distance[m][i] = distance[m][i] + (diff * diff);
		    }
		}
	    }

	    /*
	     * Przeliczamy średnie do póki wartości średnich nie przestaną się
	     * zmieniać.
	     */
	    float[][] meansRecalculate = new float[kmeans][floatColumnNames
		    .size()];
	    int[] count = new int[kmeans];
	    boolean countLock = false;
	    // for (int i = 0; i < rowCount; ++i) {
	    //
	    // /*
	    // * Najblizej danego obiektu jest srodek 'centroid'
	    // */
	    // int centroid = 0;
	    // float tmp = -1;
	    // for (int m = 0; m < kmeans; ++m) {
	    // if (tmp == -1 || distance[m][i] < tmp) {
	    // tmp = distance[m][i];
	    // centroid = m;
	    // }
	    // }
	    //
	    // ++count[centroid];
	    //
	    // /*
	    // * Sumujemy wszystkie wartosci.
	    // */
	    // for (int j = 0; j < floatColumnNames.size(); ++j) {
	    // String colName = floatColumnNames.get(j);
	    // meansRecalculate[centroid][j] = meansRecalculate[centroid][j]
	    // + (Float) data.getCell(colName, i);
	    // }
	    // }

	    for (int j = 0; j < floatColumnNames.size(); ++j) {
		String colName = floatColumnNames.get(j);

		for (int i = 0; i < rowCount; ++i) {
		    /*
		     * Najblizej danego obiektu jest srodek 'centroid'
		     */
		    int centroid = 0;
		    float tmp = -1;
		    for (int m = 0; m < kmeans; ++m) {
			if (tmp == -1 || distance[m][i] < tmp) {
			    tmp = distance[m][i];
			    centroid = m;
			}
		    }

		    if (!countLock)
			++count[centroid];

		    meansRecalculate[centroid][j] = meansRecalculate[centroid][j]
			    + (Float) data.getCell(colName, i);
		}

		countLock = true;

		for (int m = 0; m < kmeans; ++m) {
		    if (count[m] != 0)
			meansRecalculate[m][j] = meansRecalculate[m][j]
				/ count[m];
		}
	    }

	    /*
	     * Porownujemy nowe srednie ze starymi.
	     */
	    int numberOfValueChanges = 0;
	    for (int m = 0; m < kmeans; ++m) {
		for (int j = 0; j < floatColumnNames.size(); ++j) {
		    float diff = Math.abs(meansRecalculate[m][j] - means[m][j]);

		    if (means[m][j] != meansRecalculate[m][j]
			    && diff > MAX_DIFFERENCE) {
			means[m][j] = meansRecalculate[m][j];
			++numberOfValueChanges;
		    }
		}
	    }

	    changed = (numberOfValueChanges > 0) ? true : false;
	    ++iterations;
	}

	List<Object> newClasses = new ArrayList<Object>();
	for (int i = 0; i < rowCount; ++i) {
	    /*
	     * Najblizej danego obiektu jest srodek 'centroid'
	     */
	    int centroid = 0;
	    float tmp = -1;
	    for (int m = 0; m < kmeans; ++m) {
		if (tmp == -1 || distances[m][i] < tmp) {
		    tmp = distances[m][i];
		    centroid = m;
		}
	    }

	    newClasses.add(Float.valueOf(centroid + 1));
	}

	/*
	 * Tworzenie nazwy nowej kolumny oraz umieszczenie jej razem z
	 * wartościami w HashMapie.
	 */
	String prefixedName;
	if (newColumnName == null || newColumnName.isEmpty()) {
	    prefixedName = new StringBuilder(PREFIX_BASE)
		    .append(String.format(ATTRIBUTES_SUFFIX,
			    floatColumnNames.size())).append("_")
		    .append(String.format(MEANS_SUFFIX, kmeans)).toString();
	} else {
	    prefixedName = newColumnName;
	}

	Map<String, List<Object>> namedClusteredColumn = new LinkedHashMap<String, List<Object>>();
	namedClusteredColumn.put(prefixedName, newClasses);

	return namedClusteredColumn;
    }
}
